// https://www.lintcode.com/problem/scramble-string/my-submissions

class Solution {
public:
    /**
     * @param s1: A string
     * @param s2: Another string
     * @return: whether s2 is a scrambled string of s1
     */
     
    // dp
    // O（n^4）

    bool isScramble(string &s1, string &s2) {
        int n = s1.length();
        int m = s2.length();
        if (m != n)
            return false;
        // vector<vector<vector<int>>> res(n, vector<vector<int>>(n, vector<int>(n + 1, false))); 
        // 注意！debug还很难发现！
        vector<vector<vector<bool>>> res(n, vector<vector<bool>>(n, vector<bool>(n + 1, false)));
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                // res[i][j][1] == (s1[i] == s2[j]);
                res[i][j][1] = (s1[i] == s2[j]);
            }
        }
        for (int len = 2; len < n + 1; ++len)
        {
            // for (int i = 0; i < n; ++i)
            for (int i = 0; i <= n - len; ++i)
            {
                // for (int j = 0; j < n; ++j)
                for (int j = 0; j <= n - len; ++j) 
                {
                    for (int w = 1; w < len; ++w)
                    {
                        res[i][j][len] = (res[i][j][w] && res[i + w][j + w][len - w]) ||    
                            (res[i][j + len - w][w] && res[i + w][j][len - w]);
                        if (res[i][j][len]) break; //重要！
                    }
                }
            }
        }
        return res[0][0][n];
    }
    
    // 记忆化搜索
    // 92%,TLE
    // vector<vector<vector<bool>>> res;
    // vector<vector<vector<bool>>> done;
    // string ss1;
    // string ss2;
    // void calc(int i, int j, int len)
    // {
    //     if (done[i][j][len]) return;
    //     done[i][j][len] = true;
    //     if (len == 1)
    //     {
    //         res[i][j][len] = (ss1[i] == ss2[j]);
    //         return;
    //     }
      
    //     for (int w = 1; w < len; ++w)
    //     {
    //         calc(i, j, w);
    //         calc(i + w, j + w, len - w);
    //         if (res[i][j][w] && res[i + w][j + w][len - w])
    //         {
    //             res[i][j][len] = true;
    //             break;
    //         }
    //         calc(i, j + len - w, w);
    //         calc(i + w, j, len - w);
    //         // if (res[i][j + len - w][w] && res[i + w][j][len - w]); !!!直接导致判断无效
    //         if (res[i][j + len - w][w] && res[i + w][j][len - w])
    //         {
    //             res[i][j][len] = true;
    //             break;
    //         }
    //     }
    // }
    // bool isScramble(string &s1, string &s2) {
    //     int n = s1.length();
    //     int m = s2.length();
    //     if (m != n)
    //         return false;
    //     vector<vector<vector<bool>>> res1(n, vector<vector<bool>>(n, vector<bool>(n + 1, false)));
    //     vector<vector<vector<bool>>> done1(n, vector<vector<bool>>(n, vector<bool>(n + 1, false)));
    //     res = res1;
    //     done = done1;
    //     ss1 = s1;
    //     ss2 = s2;
    //     calc(0, 0, n);
    //     return res[0][0][n];
    // }
};


// before
  // sort(s1.begin(), s1.end());
        // sort(s2.begin(), s2.end());
        // return s1 == s2; 必要不充分
        // Input
        // "abcd"
        // "bdac"
        // Output
        // true
        // Expected
        // false
        
        // 个：递推只要看最后就行了：要么ab=ab 要么ab=ba，不要被任务吓到;
        // 题目只转一次
        
        
    // 法一：递推+剪枝
    // bool isScramble(string s1, string s2) {
        // if (s1 == s2)
        // {
        //     return true;
        // }
        // if (s1.length() != s2.length())
        // {
        //     cout << "here1" << endl;
        //     return false; // 剪枝
        // }
        // string ss1 = s1;
        // string ss2 = s2;
        // sort(ss1.begin(), ss1.end());
        // sort(ss2.begin(), ss2.end());
        
        // if (ss1 != ss2)
        // {
        //     return false; 
        // }
        // for (int i = 1; i < s1.length(); ++i) 
        // // 注意从1开始，不能从0，死循环;
        // // 第二位表示长度，length能取到
        // {
        //     if((isScramble(s1.substr(0, i), s2.substr(0, i)) && 
        //     isScramble(s1.substr(i), s2.substr(i))) ||
        //     (isScramble(s1.substr(0, i),  s2.substr(s2.length() - i)) && 
        //     // isScramble(s1.substr(s1.length() - i), s2.substr(0, i))))
        //     isScramble(s1.substr(i), s2.substr(0, s2.length() - i))))
        //     {
        //         return true;
        //     }
        // }
        // return false;
    // }
    
    
    
     // 法二：记忆化搜索
    // map<string, bool> memo;
    // bool isScramble(string s1, string s2) {
    //     if (memo.find(s1 + "#" + s2) != memo.end())
    //     {
    //         return memo[s1 + "#" + s2];
    //     }
    //     if (s1.length() != s2.length())
    //     {
    //         return false;
    //     }
    //     if (s1.length() == 1)
    //     {
    //         return s1 == s2;
    //     }
    //     for (int i = 1; i < s1.length(); ++i) 
    //     {
    //         if((isScramble(s1.substr(0, i), s2.substr(0, i)) && 
    //         isScramble(s1.substr(i), s2.substr(i))) ||
    //         (isScramble(s1.substr(0, i),  s2.substr(s2.length() - i)) && 
    //         // isScramble(s1.substr(s1.length() - i), s2.substr(0, i))))
    //         isScramble(s1.substr(i), s2.substr(0, s2.length() - i))))
    //         {
    //             memo[s1 + "#" + s2] = true;
    //             return true;
    //         }
    //     }
    //     memo[s1 + "#" + s2] = false;
    //     return false;   
    // }
    
    // 法三：动态规划，注意数组里面存的东西
//     bool isScramble(string s1, string s2) {
//         int n = s1.length();
//         if (s2.length() != n)
//         {
//             return false;
//         }
//         bool ***record = new bool**[n + 1];
//         for (int i = 0; i <= n; ++i)
//         {
//             record[i] = new bool*[n];
//         }
//         for (int i = 0; i <= n; ++i)
//         {
//             for (int j = 0; j < n; ++j) 
//             {
//                 record[i][j] = new bool[n];
//                 record[i][j][1] = (s1[i] == s2[j]);
//             }
//         }
//         for (int len=2; len <= n; ++len) {
//             for (int i = 0; i <= n - len; ++i)
//             {
//                 for (int j = 0; j <= n - len; ++j)
//                 {
//                     record[i][j][len] = false;
//                     for (int w = 1; w < len; ++w)
//                     {
//                         if ((record[i][j][w] && record[i + w][j + w][len - w])
//                         || (record[i][j + len - w][w] && record[i + w][j][len - w]))
//                         {
//                             record[i][j][len] = true;
//                             break;
//                         }
//                     }
//                 }
//             }
//         }
//         return record[0][0][n];
//     }
// };

